P3312 [SDOI2014]数表

P3312 [SDOI2014]数表

题解

题意

求，

$$\sum_{i = 1} ^ n \sum_{j = 1} ^ m \sigma(\gcd(i, j)) [\sigma(\gcd(i, j)) \le k]$$

$1 \le n, m \le 10 ^ 5， 1 \le T \le 2 \times 10 ^ 4$。

解法

考虑到$T$组数据显然不能每次都重新处理一遍，先不考虑限制，化一下柿子，

$$\begin{aligned} ans & = \sum_{i = 1} ^ n \sum_{j = 1} ^ m \sigma(\gcd(i, j)) \\ & = \sum_{t = 1} \sigma(t) \sum_{i = 1} ^ {\lfloor \frac{n}{t} \rfloor}\sum_{j = 1} ^ {\lfloor \frac{m}{t} \rfloor} [\gcd(i, j) = 1] \\ & = \sum_{t = 1} \sigma(t) \sum_{i = 1} ^ {\lfloor \frac{n}{t} \rfloor}\sum_{j = 1} ^ {\lfloor \frac{m}{t} \rfloor} \sum_{d | \gcd(i, j)} \mu(d) \\ & = \sum_{t = 1} \sigma(t) \sum_{d = 1} \mu(d) \sum_{i = 1} ^ {\lfloor \frac{n}{td} \rfloor}\sum_{j = 1} ^ {\lfloor \frac{m}{td} \rfloor} 1 \end{aligned}$$

加上限制柿子变为，

$$ans = \sum_{\sigma(t) \le k} \sum_{d = 1} \mu(d) \sum_{i = 1} ^ {\lfloor \frac{n}{td} \rfloor}\sum_{j = 1} ^ {\lfloor \frac{m}{td} \rfloor} 1$$

然后枚举$td$，

$$ans = \sum_{p = 1} \lfloor \frac{n}p \rfloor \lfloor \frac{m}{p} \rfloor \sum_{1 \le \sigma(d) \le k} \sigma(d) \mu({\frac{p}{d}})$$

可以先将询问离线下来，按$k$排序，树状数组动态维护即可。

时间复杂度$O(T\sqrt n \log n + n \log^2 n)$。

(注意约数和不是单调递增的(维生素b))

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e5 + 10;
const int M = 1e5;
const ll mod = (1ll << 31);

int n, m;

struct query
{
    int n, m, k, i;
    query(int n = 0, int m = 0, int k = 0, int i = 0) :
        n(n), m(m), k(k), i(i) {}
    friend bool operator < (query a, query b)
        {return a.k < b.k;}
};

query q[N];

ll ans[N];

struct BIT
{
    ll b[N];
    BIT(){memset(b, 0, sizeof(b));}
    int lowbit(int x){return x & (-x);}
    void add(int x, ll k)
    {
        for(int i = x; i <= M; i += lowbit(i))
            b[i] = (b[i] + k) % mod;
    }
    ll sum(int x)
    {
        ll s = 0;
        for(int i = x; i >= 1; i -= lowbit(i))
            s = (s + b[i]) % mod;
        return s;
    }
    ll query(int l, int r)
    {
        return (sum(r) - sum(l - 1) + mod) % mod;
    }
};

BIT bit;

int prime[N], cnt, mu[N];

bool vis[N];

struct node
{
    int i, s;
    friend bool operator < (node a, node b)
        {return a.s < b.s;}
};

node S[N];

void init()
{
    mu[1] = 1;
    for(int i = 2; i <= M; i++)
    {
        if(!vis[i])prime[++cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * prime[j] <= M; j++)
        {
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0)break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= M; i++)
        S[i].i = i;
    for(int i = 1; i <= M; i++)
        for(int j = i; j <= M; j += i)
            S[j].s = (S[j].s + i * 1ll) % mod;
    sort(S + 1, S + M + 1);
}

int main()
{
    init();
    int T; scanf("%d", &T);
    for(int i = 1; i <= T; i++)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        q[i] = query(n, m, k, i);
    }
    sort(q + 1, q + T + 1);
    for(int i = 1, j = 1; i <= T; i++)
    {
        while(S[j].s <= q[i].k && j < M)
        {
            for(int k = S[j].i; k <= M; k += S[j].i)
                bit.add(k, (S[j].s * mu[k / S[j].i] % mod + mod) % mod);
            j++;
        }
        int n = q[i].n, m = q[i].m, id = q[i].i;
        for(int l = 1, r; l <= min(n, m); l = r + 1)
        {
            r = min(n / (n / l), m / (m / l));
            ans[id] = (ans[id] + 1ll * (n / l) * (m / l) % mod * bit.query(l, r) % mod + mod) % mod;
        }
    }
    for(int i = 1; i <= T; i++)
        printf("%lld\n", ans[i]);
    return 0;
}